package com.wss.lsl.test.driven.date20211226;

import java.io.Serializable;
import java.util.Deque;
import java.util.Stack;
import java.util.concurrent.LinkedBlockingDeque;

public class SortedBtree implements Serializable {

	/**
	 * 
	 */
	private static final long serialVersionUID = 1L;
	private SortedBtree left;
	private SortedBtree right;

	private int value;

	public SortedBtree getLeft() {
		return left;
	}

	public void setLeft(SortedBtree left) {
		this.left = left;
	}

	public SortedBtree getRight() {
		return right;
	}

	public void setRight(SortedBtree right) {
		this.right = right;
	}

	public int getValue() {
		return value;
	}

	public void setValue(int value) {
		this.value = value;
	}

	/**
	 * 初始化。
	 * 
	 * @param node
	 * @param value
	 */
	public void initSortedBtree(SortedBtree node, int value) {
		if (value <= node.getValue()) {
			if (node.getLeft() != null) {
				initSortedBtree(node.getLeft(), value);
			} else {
				SortedBtree left = new SortedBtree();
				left.setValue(value);
				node.setLeft(left);
			}
			return;
		}

		if (node.getRight() != null) {
			initSortedBtree(node.getRight(), value);
		} else {
			SortedBtree right = new SortedBtree();
			right.setValue(value);
			node.setRight(right);
		}
	}

	/**
	 * 获取第二大元素。相同的元素取第二个
	 * 
	 * @return
	 */
	public SortedBtree secondMaxNode() {
		if (left == null && right == null) {
			throw new IllegalArgumentException();
		}
		if (right != null) {
			SortedBtree p1 = this;
			SortedBtree p2 = right;
			SortedBtree r = right.right;
			return rightSecondMax(p1, p2, r);
		}

		return max(left);
	}

	/**
	 * 右边第二大的元素
	 * 
	 * @param p1
	 * @param p2
	 * @param r
	 * @return
	 */
	private SortedBtree rightSecondMax(SortedBtree p1, SortedBtree p2, SortedBtree r) {
		if (r != null) {
			return rightSecondMax(p2, r, r.right);
		}
		if (p2.left == null) {
			return p1;
		}

		// 获取左子树最大的元素
		return max(p2.left);
	}

	/**
	 * 
	 * 
	 * @param node
	 * @return
	 */
	private SortedBtree max(SortedBtree node) {

		return max(node, node.right);
	}

	private SortedBtree max(SortedBtree p, SortedBtree r) {
		if (r == null) {
			return p;
		}

		return max(r, r.right);
	}

	/**
	 * 回旋打印二叉树。奇数层节点，从左往右；偶数层节点，从右往左。
	 */
	public void circleRoundPrint() {
		
		Deque<SortedBtree> queue = new LinkedBlockingDeque<>();
		Stack<SortedBtree> stack = new Stack<>();
		
		queue.add(this);
		while(!queue.isEmpty()) {
			while(!queue.isEmpty()) {
				SortedBtree tree = queue.poll();
				print(tree);
				if (tree.left != null) {
					stack.push(tree.left);
				}
				if (tree.right != null) {
					stack.push(tree.right);
				}
			}
			
			while(!stack.isEmpty()) {
				SortedBtree tree = stack.pop();
				print(tree);
				if (tree.right != null) {
					queue.addFirst(tree.right);
				}
				if (tree.left != null) {
					queue.addFirst(tree.left);
				}
			}
		}
	}
	
	private void print(SortedBtree node) {
		System.out.print(node.value);
		System.out.print(" ");
		
	}
}
